This invention relates to numeric calculation, and particularly to methods of determining the nearest neighbor of a selected point from among a set of different points.
Computer software applications sometimes require a determination of which of a set of points in multidimensional mathematical xe2x80x9cspacexe2x80x9d is closest to a given target point. Each point has a number of variable parameters, each of which may vary within a range to indicate a particular quality, quantity, degree or attribute of that parameter for an element to which the target point corresponds. Each parameter is abstractly considered as a dimension, and the value of that parameter is abstractly considered as the location along an axis corresponding to that dimension. The set of points are candidate points, each representing a particular standardized instance of known characteristics, and which the application can rely on preselected heuristics for processing.
An example of the above system is a software application or module for processing or compressing image files. Such applications may make a pixel-by-pixel analysis, and use different compression algorithms or processes depending on the context of each pixel. The context of each pixel is generally defined in terms of the pixel""s relation to its neighbors, and provides an indication of what processing mode is best suited to that region of the image to provide a suitable tradeoff of compression efficiency and image quality. For instance, one context model is a pixel that is identical to all adjacent pixels. For this, a compression-efficient algorithm may represent a multi-pixel block by a single color value, plus the definition of the boundaries of the block. Another context model may be a pixel that differs extremely from all adjacent pixels. This may be processed by a different algorithm that preserves the detail, and which is less compression efficient. Another context model may represent a pixel at a sharp boundary of flat regions, which is used to locate a division between large blocks of similar color data. A multitude of other context models are generated, each associated with a given compression or processing technique that is proven to be effective for that type of image characteristics.
Together, this set of context models is considered to be a set of candidate points, each with a value for each of several (or numerous) parameters. When processing an actual image, the application determines for each pixel which of the context models (or candidate points) is most similar to the pixel. This is done by generating a similar point in multi-demensional space for each pixel. Because the pixel is unlikely to be identical to one of the limited number of models, the application must determine which of the models is most similar to the pixel.
Assuming that all parameters are scaled to be of equal importance, the application simply determines which of the candidate points is mathematically spatially nearest to the target point corresponding to the pixel being analyzed. (Note that the spatial nearness of these points in a conceptual xe2x80x9cspacexe2x80x9d is essentially unrelated to the image xe2x80x9cspacexe2x80x9d in which the pixel and its neighbors reside; searching for the nearest point is not to be considered as searching for a nearby pixel.)
Existing systems achieve this calculation and determination of the nearest candidate point to the target point by conventional mathematical calculations in which the distance from the target point to each candidate point is determined by Pythagorean geometry. The candidate point with the smallest distance is determined to be most similar, and the processing algorithm associated with that candidate is applied for the pixel corresponding to the target point.
While effective, such systems have the disadvantage of requiring significant calculation resources, particularly as the number of dimensions and points increases. The calculations require many multiplication operations, which are relatively processor-intensive. For example, in a scenario with 10,000 candidate points and 23 parameters or dimensions, 230,000 multiplication operations would be required, plus a comparable number of additions or subtractions. This is believed to generate noticeable delay on typical computers.
The present invention overcomes the limitations of the prior art by providing a method of determining a near neighbor to a target point in multidimensional space from among a set of candidate points. The method includes generating a matrix of bins and identifying a first bin that contains the target point. The first bin is searched for a first candidate point, and a set of proximate bins selected from the matrix are identified. Each of the proximate bins has at least a portion of space potentially closer to a first selected point in the first bin than is a second selected point in the first bin. the proximate bins has at least a portion of space potentially closer to a first selected point in the first bin than is a second selected point in the first bin.